package erChaShuFuXi;


import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //创建二叉树
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;

        return A;
    }

    public static int count=0;
    //获取树节点个数
    public int size(TreeNode root) {
        if(root==null){
            return 0;
        }
        return  size(root.left)+size(root.right)+1;
    }

    public void size1(TreeNode root){
        if(root==null){
            return;
        }
        count++;
        size1(root.left);
        size1(root.right);
    }

    //获取叶子节点
    int leafsize=0;
    public boolean getLeafNodeCount(TreeNode root) {
        if(root==null){
            return false;
        }
        if(root.left==null&&root.right==null){
            leafsize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return false;
    }

    //获取叶子节点有返回值接收
    public int getKLevelNodeCount(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            //遇到一个叶子节点就返回1，然后1+ 下一个叶子节点
            return 1;
        }
        return getKLevelNodeCount(root.left)+
                getKLevelNodeCount(root.right);
    }

    public int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftheight=getHeight(root.left);
        int rightheight=getHeight(root.right);
        return leftheight>leftheight?leftheight+1:rightheight+1;
    }


    public TreeNode find(TreeNode root, char val) {
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode left1= find(root.left, val);
        if(left1.val==val){
            return left1;
        }
        TreeNode right1=find(root.right,val);
        if(right1.val==val){
            return right1;
        }
        return null;
    }


    public void levelOrder(TreeNode root) {
        if (root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    public List<List<Character>> levelOrder2(TreeNode root){
        List<List<Character>> list=new LinkedList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size= queue.size();
            LinkedList<Character> ret=new LinkedList<>();
            while(size!=0){
                TreeNode cur=queue.poll();
                ret.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
        list.add(ret);
        }
        return list;
    }




    public boolean isCompleteTree(TreeNode root) {
        if (root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode ret = queue.poll();
            if (ret != null) {
                queue.offer(ret.left);
                queue.offer(ret.right);
            }else {
                break;
            }
        }

        while (!queue.isEmpty()){
            TreeNode peek=queue.peek();
            if(peek!=null){
                return false;
            }else{
                queue.poll();
            }
        }
        return true;
    }
}
